package solution.dp;

import org.junit.Assert;
import org.junit.Test;

/**
 * http://www.sureinterview.com/shwqst/123005
 * 
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class FibonacciNumber {

	long fb3[];

	long fn[] = new long[] { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,
			377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,
			75025, 121393, 196418, 317811, 514229, 832040 };

	/**
	 * Fibonacci number. DP version. http://www.sureinterview.com/shwqst/123005
	 * 
	 * @param n
	 * @return Fn
	 */
	long Fn_non_recursive1(int n) {
		if (n <= 0)
			return 0;
		if (n == 1)
			return 1L;

		long f[] = new long[n + 1];

		f[0] = 0;
		f[1] = 1;
		for (int i = 2; i <= n; i++) {
			f[i] = f[i - 1] + f[i - 2];
		}
		return f[n];
	}

	/**
	 * Fibonacci number. DP version with space reduced.
	 * http://www.sureinterview.com/shwqst/123005
	 * 
	 * @param n
	 * @return Fn
	 */
	long Fn_non_recursive2(int n) {
		if (n <= 0)
			return 0;
		if (n == 1)
			return 1L;

		long fn2 = 0;
		long fn1 = 1;
		long fn = fn1 + fn2;

		for (int i = 2; i <= n; i++) {
			fn = fn1 + fn2;
			fn2 = fn1;
			fn1 = fn;
		}

		return fn;
	}

	/**
	 * Fibonacci number. Recursive version.
	 * http://www.sureinterview.com/shwqst/123005
	 * 
	 * @param n
	 * @return Fn
	 */
	long Fn_recursive(int n) {
		// base
		if (n <= 0)
			return 0;
		if (n == 1)
			return 1L;

		// induction
		return Fn_recursive(n - 1) + Fn_recursive(n - 2);
	}

	/*
	 * Top-down with divide and conquer
	 * http://www.sureinterview.com/shwqst/123005
	 */
	long Fn3(int n) {
		fb3 = new long[(n < 2 ? 3 : n + 1)];
		fb3[1] = fb3[2] = 1L;
		long res = Fn3_rec(n);
		return res;
	}

	long Fn3_rec(int n) {
		if (n <= 0)
			return 0;
		if (fb3[n] > 0)
			return fb3[n];

		int i = (n >> 1) + 1;
		fb3[n] = Fn3_rec(n - i) * Fn3_rec(i - 1) + //
				Fn3_rec(n - i + 1) * Fn3_rec(i);
		return fb3[n];
	}

	@Test
	public void za_Fn() {
		for (int i = 0; i < fn.length; i++) {
			Assert.assertEquals(fn[i], Fn_recursive(i));
		}

		for (int i = 0; i < 30; i++) {
			long fn1 = Fn_non_recursive1(i);
			long fn2 = Fn_non_recursive2(i);
			long fn3 = Fn3(i);
			long fr = Fn_recursive(i);
			Assert.assertEquals(fr, fn1);
			Assert.assertEquals(fr, fn2);
			Assert.assertEquals(fr, fn3);
			System.out.println(fn3);
		}
	}
}
